/**
 * 5-14、5-15、5-16：
 * 修改排序程序，使它具有以下功能：
 * 添加-r标记，该标记表明，以逆序(递减)方式排序。要保证-r和-n能够组合在一起使用；
 * 添加-f标记，使得排序过程不考虑字母大小写之间的区别。例如，比较a和A时认为它们相等；
 * 添加选项-d（代表目录顺序），该选项表明，只对字母、数字和空格进行比较。要保证该选项可以和-f组合在一起使用；
**/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "./alloc/alloc.h"


#define MAXLINES 5000		// max #lines to be sorted

char *lineptr[MAXLINES];	// pointers to text lines

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void myqsort(void *lineptrp[], int left, int right, int (*comp)(void *, void *), int order);
int numcmp(char *, char *);			// 数字比较
int charcmp(const char *, const char *);	// 字符比较不区分大小
int listcmp(const char *, const char *);	// 按照目录顺序排序
int list_charcmp(const char *, const char *);	// 按照目录顺序，不区分大小写排序
void swap(void *v[], int i, int j);

// sort input lines
int main(int argc, char *argv[])
{
	int c;
int nlines;		// number of input lines read
	int numeric = 0;	// 1 if numberic sort  2 是不区分大小写
	int sort_order = -1;	// 排序的次序(-1 升序 1 降序)
	int dir = 0;		// 目录顺序

	// 解析参数
	while(--argc > 0 && (*++argv)[0] == '-')
	{
		while(c = *++argv[0])
		{
			switch(c)
			{
			case 'n':			// 数字排序
				numeric = 1;
				break;
			case 'f':			// 不区分大小写
				numeric = 2;		
				break;
			case 'd':			// 目录排序
				dir = 1;		
				break;
			case 'r':			// 降序
				sort_order = 1;
				break;
			default:
				printf("find: illegal option %c\n", c);
				argc = 0;
				break;
			}
		}
	}

	if((nlines = readlines(lineptr, MAXLINES)) >= 0)
	{
		myqsort((void**) lineptr, 0, nlines - 1, (int (*)(void*, void*))((!numeric) ? strcmp : (numeric == 1) ? numcmp : (numeric == 2 && dir == 0) ? charcmp : (dir == 1 && numeric == 2) ? list_charcmp : listcmp), sort_order);
		printf("-----------------\n");
		writelines(lineptr, nlines);
		return 0;
	}
	else
	{
		printf("input too big to sort\n");
		return 1;
	}
}

// qsort: sort v[left] ... v[right] into increasing order
void myqsort(void *v[], int left, int right, int(*comp)(void *, void *), int order)
{
	int i, last;
	void swap(void *v[], int, int);
	if(left >= right)	// do nothing if array contains
		return;		// fewer than two elements
	swap(v, left, (left + right) / 2);
	last = left;
	for(i = left + 1; i <= right; i++)
		if((*comp)(v[i], v[left]) == order)
			swap(v, ++last, i);
	swap(v, left, last);
	myqsort(v, left, last - 1, comp, order);
	myqsort(v, last + 1, right, comp, order); 
}

// numcmp: compare s1 and s2 numerically
int numcmp(char *s1, char *s2)
{
	double v1, v2;
	
	v1 = atof(s1);
	v2 = atof(s2);
	if(v1 < v2)
		return -1;
	else if(v1 > v2)
		return 1;
	else 
		return 0;
}

void swap(void *v[], int i, int j)
{
	void *temp;

	temp = v[i];
	v[i] = v[j];
	v[j] = temp;
}

#define MAXLEN 1000	// max length of any input line

int Getline(char *, int);

// readlines: read input lines
int readlines(char *lineptr[], int maxlines)
{
	int len, nlines;
	char *p, line[MAXLEN];

	nlines = 0;
	while((len = Getline(line, MAXLEN)) > 0)
		if(nlines >= maxlines || (p = alloc(len)) == NULL)
			return -1;
		else
		{
			line[len - 1] = '\0';		// delete newline
			strcpy(p, line);
			lineptr[nlines++] = p;
		}
	return nlines;
}

// writelines: write output lines
void writelines(char *lineptr[], int nlines)
{
	int i;
	for(i = 0; i < nlines; i++)
		printf("%s\n", lineptr[i]);
}

// Getline: get line into s, return length
int Getline(char s[], int lim)
{
	int c, i;

	i = 0;
	while(--lim > 0 && (c = getchar()) != EOF && c != '\n')
		s[i++] = c;
	if(c == '\n')
		s[i++] = c;
	s[i] = '\0';
	return i;
}

int charcmp(const char * s, const char * t)
{
	while(tolower(*s) == tolower(*t))
	{
		s++;
		t++;
	}	
	
	if(tolower(*s) < tolower(*t))
		return -1;
	else if(tolower(*s) > tolower(*t))
		return 1;
	else
		return 0;
} 

int listcmp(const char *s, const char *t)
{
	int c1, c2;

	do
	{
		while(!isalnum(*s) && *s != ' ' && *s != '\0')
			s++;
		while(!isalnum(*t) && *t != ' ' && *t != '\0')
			t++;
		if(*s == '\0' && *t == '\0')
			return 0;
		c1 = *s;
		s++;
		c2 = *t;
		t++;
	}while(c1 == c2);
	
	if(c1 < c2)
		return -1;
	else if(c1 > c2)
		return 1;
	else 
		return 0;
}

int list_charcmp(const char *s, const char *t)
{
	int c1, c2;

        do
        {
                while(!isalnum(*s) && *s != ' ' && *s != '\0')
                        s++;
                while(!isalnum(*t) && *t != ' ' && *t != '\0')
                        t++;
                if(*s == '\0' && *t == '\0')
                        return 0;
                c1 = tolower(*s);
                s++;
                c2 = tolower(*t);
                t++;
        }while(c1 == c2);

        if(c1 < c2)
                return -1;
        else if(c1 > c2)
                return 1;
        else
                return 0;

}
